from typing import List

def lower_bound(nums:List[int],target:int)->int:
    left,right=0,len(nums)-1
    while left<=right:
        mid =(left+right)//2
        if nums[mid] >=target:
            right=mid-1
        else:
            left=mid+1
    return left
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        ans = []
        for spell in spells:
            # 计算最小需要的药水值：spell * potion >= success → potion >= success / spell
            # 用浮点数避免整数除法误差（例如success=7, spell=3时，7/3≈2.333，potion需≥3）
            min_potion = success / spell
            # 找到第一个>=min_potion的位置
            pos = lower_bound(potions, min_potion)
            # 符合条件的数量：从pos到末尾的所有元素
            ans.append(len(potions) - pos)
            # # 修正1：计算每个药水乘以spell的结果（用列表推导式，而非列表重复）
            # potions2 = [spell * p for p in potions]
            # # 修正2：获取第一个>=success的位置
            # pos = lower_bound(potions2, success)
            # # 修正3：符合条件的数量 = 总长度 - 第一个符合条件的位置
            # ans.append(len(potions2) - pos)
        return ans
'''
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect_left(potions, success / x) for x in spells]

作者：灵茶山艾府
链接：https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/solutions/1595712/by-endlesscheng-1kbp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''

